package offer.zixing.chapter05;

import java.util.Arrays;
import java.util.List;

/**
 * 最小时间差
 *
 * 给你一组范围在00:00至23:59的时间，求它们任意两个时间之间的最小时间差。
 * 例如，输入时间数组["23:50", "23:59", "00:00"]，
 * "23:59"和"00:00"之间只有1分钟间隔，是最小的时间差
 */
public class Test035 {

    public static void main(String[] args) {
        System.out.println(findMinDifference(Arrays.asList("23:59", "00:00")));
//        System.out.println(findMinDifference(Arrays.asList("12:12", "00:13")));
    }

    public static int findMinDifference(List<String> timePoints) {
        // 一天有 1440 分钟
        if (timePoints.size() > 1440) {
            return 0;
        }
        boolean minuteFlags[] = new boolean[1440];
        for (String time : timePoints) {
            String t[] = time.split(":");
            int minute = Integer.parseInt(t[0]) * 60 + Integer.parseInt(t[1]);
            if (minuteFlags[minute]) {
                return 0;
            }
            minuteFlags[minute] = true;
        }
        return findMinDifference(minuteFlags);
    }

    private static int findMinDifference(boolean minuteFlags[]) {
        int minDiff = minuteFlags.length - 1;
        int prev = -1;
        int first = minuteFlags.length - 1;
        int last = -1;
        for (int i = 0; i < minuteFlags.length; i++) {
            if (minuteFlags[i]) {
                if (prev >= 0) {
                    minDiff = Math.min(i - prev, minDiff);
                }
                prev = i;
                first = Math.min(i, first);
                last = Math.max(i, last);
            }
        }
        minDiff = Math.min(first + minuteFlags.length - last, minDiff);
        return minDiff;
    }
}
